package randomthoughts.dp;

/** leetCode:115
 * @author tongchen
 * @create 2023-05-09 20:06
 */
public class DifferentSubquence {
    //动规五部曲：dp[i][j]:在s中以i为结尾 在t中以j为结尾的情况下 s可以匹配t的个数
    //递推公式if(s[i-1]=t[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 不相等：dp[i][j]=dp[i-1][j]
    //遍历顺序：从前往后进行遍历
    //初始化：dp[0][j]=0 dp[i][0]=1
    public int numDistinct(String s, String t) {
        //创建dp数组
        int[][]dp=new int[s.length()+1][t.length()+1];
        //初始化
        for(int i=0;i<=s.length();++i){
            dp[i][0]=1;
        }
        //进行遍历
        for(int i=1;i<=s.length();++i){
            for(int j=1;j<=t.length();++j){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}
